package com.primaryAlgorithm;



/**
 * Description: 多链表排序
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-26 14:22:14
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-26     张李鑫                     1.0         1.0 Version
 */
public class MergeKLists {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }


    //##################################先实现普通的归并排序 mergeArr


    /**
     * <p>
     * 递归
     * </p>
     *
     * @param arr
     * @param L
     * @param R
     * @return void
     * @Author zlx
     * @date 2021/9/26
     */
    public static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        mergeArr(arr, L, mid, R);
    }


    public static void mergeArr(int[] arr, int L, int mid, int R) {
        int p = L;
        int p1 = mid + 1;
        int index = 0;
        int[] merge = new int[R - L + 1];
        while (p <= mid && p1 <= R) {
            merge[index++] = arr[p] < arr[p1] ? arr[p++] : arr[p1++];
        }
        while (p <= mid) {
            merge[index++] = arr[p++];
        }
        while (p1 <= R) {
            merge[index++] = arr[p1++];
        }
        for (int i = 0; i < merge.length; i++) {
            arr[L++] = merge[i];
        }
    }

    /**
     * <p>
     * 非递归
     * </p>
     *
     * @param arr
     * @param L
     * @param R
     * @return void
     * @Author zlx
     * @date 2021/9/26
     */
    public static void process1(int[] arr, int L, int R) {
        int mergeSize = 1;
        while (mergeSize <= R) {
            int left = 0;
            while (left <= R) {
                if (mergeSize > R - left) {
                    break;
                }
                int mid = left + mergeSize - 1;
                int right = mid + Math.min(mergeSize, R - mid);
                mergeArr(arr, left, mid, right);
                left = right + 1;
            }
            if (mergeSize << 1 > R) {
                break;
            }
            mergeSize <<= 1;
        }
    }


    public ListNode mergeKLists(ListNode[] lists) {
        int right = lists.length - 1;
        int mergeSize = 1;
        while (mergeSize <= right) {
            int left = 0;
            while (left <= right) {
                if (mergeSize >= right - left) {
                    break;
                }
                int mid = left + mergeSize - 1;
                int end = mid + Math.min(mergeSize, right - mid);
                mergeNode(lists, left, mid, right);
                left = end + 1;
            }
            if (mergeSize << 1 > right) {
                return lists[0];
            }
            mergeSize <<= 1;
        }

        return lists[0];
    }

    private void mergeNode(ListNode[] lists, int left, int mid, int right) {
        int p=left;
        int p1=mid+1;
        while (p<=mid&&p1<=right){

        }



    }

    public static void main(String[] args) {
    }
}
